package com.lfg.leetcode.leetcode100;


import java.util.HashMap;
import java.util.Map;

public class LRUCache {


    int cnt = 0;
    Map<Integer, Entry> data = null;
    int capacity;
    Entry head;
    Entry tail;

    public LRUCache(int capacity) {
        this.data = new HashMap<>(capacity);
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2 /* 缓存容量 */);

        cache.put(2, 1);
        cache.put(1, 1);
        cache.put(2, 3);    // 该操作会使得密钥 2 作废
        cache.put(4, 1);    // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));       // 返回 -1 (未找到)
        System.out.println(cache.get(2));       // 返回  3


//        cache.put(1, 1);
//        cache.put(2, 2);
//        System.out.println(cache.get(1));     // 返回  1
//        cache.put(3, 3);    // 该操作会使得密钥 2 作废
//        System.out.println(cache.get(2));       // 返回 -1 (未找到)
//        cache.put(4, 4);    // 该操作会使得密钥 1 作废
//        System.out.println(cache.get(1));       // 返回 -1 (未找到)
//        System.out.println(cache.get(3));       // 返回  3
//        System.out.println(cache.get(4));       // 返回  4
    }

    public int get(int key) {
        if (null == data) {
            return -1;
        }
        Entry entry = data.get(key);
        if (null == entry) {
            return -1;
        }
        updateHead(entry);
        return entry.value;
    }

    private void updateHead(Entry entry) {
        if (head == entry) {
            return;
        }
        Entry pre = entry.pre;
        Entry next = entry.next;
        pre.next = next;
        if (null != next) {
            next.pre = pre;
        } else {
            tail = pre;
            tail.next = null;
        }
        head.pre = entry;
        entry.next = head;
        head = entry;
        entry.pre = null;
    }

    public void put(int key, int value) {
        Entry entry = data.get(key);
        if (null != entry) {
            entry.value = value;
            updateHead(entry);
            return;
        }
        entry = new Entry(key, value);
        data.put(key, entry);
        if (null == head) {
            head = entry;
            tail = entry;
            cnt++;
            return;
        }
        head.pre = entry;
        entry.next = head;
        head = entry;

        if (cnt >= capacity) {
            Entry pre = tail.pre;
            data.remove(tail.key);
            tail = pre;
            pre.next = null;
            return;
        }
        cnt++;
    }

    class Entry {
        int key;
        int value;

        Entry pre;
        Entry next;

        Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
